package leetcode_滑动窗口;

import java.util.Arrays;

/**
 * 旋转函数
 * 算法：滑动窗口 + 前缀和
 * 将 nums 延长至原来的两倍
 * 窗口大小为 n(nums 的长度), 每次往后移
 * [k, k + n - 1], 往后移动, +(n - 1) * nums[k + n] - 中间的数
 * 中间的数 = nums[k + 1] + ... + nums[k + n - 1], 使用前缀和来求
 *
 * @author yezh
 * @date 2023/2/6 22:09
 */
public class _396 {

    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n * 2 + 10];
        for (int i = 1; i <= 2 * n; i++) prefix[i] = prefix[i - 1] + nums[(i - 1) % n];
        System.out.println(Arrays.toString(prefix));
        int ans = 0;
        for (int i = 0; i < n; i++) ans += i * nums[i];
        for (int i = n, cur = ans; i < 2 * n; i++) {
            cur += (n - 1) * nums[i % n];
            int mid = prefix[i] - prefix[i - n + 1];
            cur -= mid;
            System.out.println(mid);
            if (cur > ans) ans = cur;
        }
        return ans;
    }

}
